BZOJ3597【SCOI2014】方伯伯运椰子 <费用流>

Problem

【SCOI2014】方伯伯运椰子

Description

Input

第一行包含二个整数,。
接下来行代表条边，表示这个交通网络。
每行六个整数，表示。
接下来一行包含一条边，表示连接起点的边。

Output

一个浮点数，保留二位小数。表示答案，数据保证答案大于。

Sample Input

5 10
1 5 13 13 0 412
2 5 30 18 396 148
1 5 33 31 0 39
4 5 22 4 0 786
4 5 13 32 0 561
4 5 3 48 0 460
2 5 32 47 604 258
5 7 44 37 75 164
5 7 34 50 925 441
6 2 26 38 1000 22

Sample Output

103.00

HINT

，，，，，。

标签：费用流

Solution

妙不可言的费用流。

首先肯定需要二分答案，设当前答案是，那么第条边压缩流量花费，扩容流量花费。

对于二分后的，发现修改的同时维护流量守恒比较麻烦，不妨考虑先将所有流量都退掉，随后再逐一把不用退的流量增广回来，这样每次增广都可以保证流量守恒。那么初始费用为。

建模：
对于原图的第条边：

• ，流量，费用
• 若，则，流量，费用

这样跑最小费用最大流后判断是否成立即可判断是否有。

正确性：
由于跑费用流，会优先增广费用小的边，而，因此第一类边比第二类边小，一定会先走第一类边补到原先流量后再继续走第二类边扩容。

本文参考的题解。

Code

#include <bits/stdc++.h>
#define MAX_N 100000
#define MAX_M 100000
#define EPS 1e-5
#define INF 0x3f3f3f3f
#define mid ((l+r)/2)
using namespace std;
typedef double dnt;
template <class T>
inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
struct node {int v, c, nxt; dnt w;} E[MAX_M+5];
struct edge {int u, v, a, b, c, d;} e[MAX_M+5];
int n, m, s, t, cnt, pr[MAX_N+5], cr[MAX_N+5];	dnt mic, tot;
void init() {s = n+1, t = n+2, cnt = 0, mic = tot = 0.0, memset(pr, -1, sizeof pr);}
void insert(int u, int v, int c, dnt w) {E[cnt] = (node){v, c, pr[u], w}, pr[u] = cnt++;}
void addedge(int u, int v, int c, dnt w) {insert(u, v, c, w), insert(v, u, 0, -w);}
bool SPFA() {
    queue <int> que;	bool inq[MAX_N+5];	memset(inq, false, sizeof inq);
    dnt d[MAX_N+5];	int cr[MAX_N+5];	for (int i = 1; i <= t; i++) d[i] = INF;
    d[s] = 0, que.push(s), inq[s] = true, memset(cr, -1, sizeof cr);
    while (!que.empty()) {
        int u = que.front();	que.pop(), inq[u] = false;
        for (int i = pr[u]; ~i; i = E[i].nxt) {
            int v = E[i].v, c = E[i].c;	dnt w = E[i].w;
            if (c && d[u]+w < d[v]) {
                d[v] = d[u]+w, cr[v] = i;
                if (!inq[v]) que.push(v), inq[v] = true;
            }
        }
    }
    if (fabs(d[t]-INF) <= EPS) return false;	int flow = INF;
    for (int i = cr[t]; ~i; i = cr[E[i^1].v]) flow = min(flow, E[i].c);
    for (int i = cr[t]; ~i; i = cr[E[i^1].v]) E[i].c -= flow, E[i^1].c += flow;
    mic += 1.0*flow*d[t];	return true;
}
bool chk(dnt tans) {
    init();
    for (int i = 1; i <= m; i++)
        addedge(e[i].u, e[i].v, e[i].c, e[i].d-e[i].a-tans);
    for (int i = 1; i <= m; i++) if (e[i].u^s)
        addedge(e[i].u, e[i].v, INF, e[i].b+e[i].d+tans);
    for (int i = 1; i <= m; i++)
        tot += (e[i].a-e[i].d+tans)*e[i].c;
    while (SPFA()) ;	return tot+mic <= -EPS;
}
dnt bi_search(dnt l, dnt r) {
    dnt ret = -1.0;
    while (r-l >= EPS)
        if (!chk(mid)) r = mid;
        else ret = mid, l = mid;
    return ret;
}
int main() {
    read(n), read(m);
    for (int i = 1; i <= m; i++)
        read(e[i].u), read(e[i].v), read(e[i].a), 
        read(e[i].b), read(e[i].c), read(e[i].d);
    return printf("%.2lf", bi_search(0.0, 30000.0)), 0;
}